Given a string s, return the longest palindromic substring in s.

給一個 string 回傳該 string 最長的 palindromic substring.

Example

Input: s = "babad"
Output: "bab" || "aba"

Input: s = "cbbd"
Output: "bb"

Thanking

目的是要找到最長的 palindromic substring，可以使用 for 迴圈把每一個 substring 找出來並判斷哪一個是最長的，[[b], [ba], [bab], [baba], [babad], [a], [ab], [aba], ....] 但這種方法的時間複雜度為 O(n^3) 太慢了，所以可以用 dynamic programming 減少時間複雜度。

Step

基數

指定一個 chart 後檢查他的左右邊的 chart 是否是相等的

如果是一樣的就在往旁邊檢查

如果找到兩邊不相等的時候則代表這個 palindromic substring 的長度。

偶數

指定一個 chart 後檢查他旁邊的 chart 是否相等

如果相等則在往旁邊檢查

一直往旁邊移動直到找到這個 chart 和指定的 chart 不同的時候就代表這個 palindromic substring 的長度。

Coding

var longestPalindrome = function (s) {
    let res = [0, 1];
    for (let i = 0; i < s.length; i++) {
        const even = helper(i - 1, i, s);                           // (1)
        const odd = helper(i - 1, i + 1, s);                        // (2)
        const type = even[2] > odd[2] ? even : odd;                 // (3)
        res = res[1] - res[0] > type[1] - type[0] ? res : type;     // (4)
    }
    return s.substring(res[0], res[1]);
}

function helper(l, r, s) {
    if (l < 0 || r > s.length) return [l + 1, r];

    while (l >= 0 && r < s.length) {
        if (s[l] === s[r]) {
            l--;
            r++;
        } else {
            break;
        }
    }
    return [l + 1, r, r - l + 1];                                    // (5)
}

• (1): 找到偶數的最長 substring
• (2): 找到基數的最長 substring
• (3): 比較偶數和基數的 substring 哪一個比較長
• (4): 將比較長的 substring 暫存 res
• (5): 如果發現左邊的 chart 和右邊的 chart 不同則回傳 [左邊的index, 右邊的index, 左右index中間有多少的 chart]

Time complexity: O(n^2)